//正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
//
//
//
// 示例 1：
//
//
//输入：n = 3
//输出：["((()))","(()())","(())()","()(())","()()()"]
//
//
// 示例 2：
//
//
//输入：n = 1
//输出：["()"]
//
//
//
//
// 提示：
//
//
// 1 <= n <= 8
//
//
//
//
//
// 注意：本题与主站 22 题相同： https://leetcode-cn.com/problems/generate-parentheses/
//
// Related Topics 字符串 动态规划 回溯 👍 73 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function generateParenthesis(n: number): string[] {

    function backtracking(temp,left,right) {
        if (temp.length === n * 2) {
            res.push(temp)
            return
        }
        //? 必须严格右括号剩余数量必须大于剩余左括号数量，我们才能选右括号
        if (left > 0) backtracking(temp + '(',left - 1,right)
        if (right > left) backtracking(temp + ')',left,right - 1)
    }
    let res: string[] = []
    backtracking('',n,n)
    return res

};
//leetcode submit region end(Prohibit modification and deletion)
